模拟赛题解/2025.8.22 模拟赛

T1-那头与分配（distribute）

题面

有一棵有 $n$ 个节点的树，树上每个节点有权值 $c$，每次操作可以将一个点上的权值部分转移到相邻点。

问最后是否能使每个结点的权值相等。

$2\leq n\leq2\times10^5,0\leq c\leq10^9$。

题解

注意到一条边不会产生贡献当且仅当其两侧的头的个数平均值相等。

对于产生贡献的边，也可以计算出这条边会转移的权值的数量。

考虑得到一个合法顺序：随便选一个点为根，然后先把从深往浅把大于平均值的子树往根转移，再从浅往深向小于平均值的子树转移。

容易发现这样做任意时刻转移的 $k\leq c_u$， 故方案合法。

T2-那头与锻炼（train）

题面

一棵树上有 $n$ 个权值不同的点，一开始有一个那头位于树上权值最大的点上。

每次可以选择在一个点上放置障碍，如果那头所在的点被放置障碍，则它会沿简单路径移动到能到达的点中权值最大的一个点上。

求能达成的那头的最大移动距离和。

题解

分析：考虑到因为给出的是一棵树，因此一旦离开某个点，就不可能到达与该点相连的其他点。

基于这一性质，实际上每次移动都会将猫的移动范围限制在上一个点的某棵子树内。

1. 官 sol

   考虑时间倒流，用并查集将几个子树合并成一个，维护其贡献，树上 dp，复杂度 $O(n\log n)$

2. 特殊做法

   本质上就是搜索，传递状态为 $u$，搜索以 $u$ 为根的子树内，从该子树内权值最大的点开始能达到的最长移动距离和。

   在计算完以 $v$ 为根的子树之后直接将这一子树删去，然后再对剩余部分直接计算贡献，可以发现实际上就是在计算在以 $u$ 为根的子树内而在以 $v$ 为根的子树外的点的贡献。

   用线段树维护 dfn 进行删点（将权值更改为 $0$）和查询区间最大值操作即可。

T3-那头与串串（string）

题面

对于一个字符串，若其可以由多于一个相同的字符串相连构成，则称其为好的字符串。

求对于一个字符串 $S$，最少需要删除几个点才能使该字符串变成好的字符串。

$1\leq|S|\leq100$，保证 $S$ 由小写字母构成。

题解

设最后被分为 $k$ 段，考虑到对 $k$ 进行分开处理。

当 $k$ 较小时，直接枚举最终得到的字符串的分界点，对所有被分开的字符串求 LCS，可以使用 dp 解决，复杂度 $O(n^{2k-1})$。

当 $k$ 较大时，因为单个循环节的长度不会太大，所以考虑枚举 $T$，即单个循环节，贪心地在 $S$ 中匹配 $T$，复杂度为 $O(nk2^{\frac{k}{2}})$。

对于 $k=2,3$ 使用第一种，对于 $k\geq5$ 使用第二种，复杂度即为 $O(n^5+n2^{\frac{n}{5}}$，跑得飞快。

T4-那头与陷阱（trap）

题面

在一个数轴上有 $n$ 个陷阱，每个陷阱占据了 $[l_i,r_i]$ 的所有位置。

有两种行动方式：

第一种是向右一个单位，花费 $A$ 的时间。

第二种是向右 $D$ 个单位，花费 $B$ 的时间。

每次移动都需要移动到的位置不能被陷阱占据，$A,B,D$ 给定。

共有 $q$ 个计划，第 $i$ 个计划是从初始位置 $i$ 移动到位置 $x_i$，求对于每个计划，完成计划的最短时间，如果不能完成计划，输出 $-1$。

题解

根据 $D\times A$ 和 $B$ 的大小关系分类讨论。

较为简单的情况是 $D\times A\leq B$：此时需要最小化跳跃次数。设 $f_i$ 表示到达 $i$ 需要最少跳跃几次。转移是简单的 $f_i=\min(f_i-1,f_{i-d}+1)$。尝试分析 $f_i$ 的结构。对于一段可以到达 的区间，无法到达的位置构成一个前缀。

实际上，剩余部分的 fi 值是相等的，也就是在一 段内不存在一个位置 $j>i$ 使得 $f_j−d<f_i$。可以归纳证明，假设前 $i$ 段每段相等且总体递增，那么第 $i+1$ 段也满足上述条件。快速维护是简单的。

对于 $D\times A>B$，$f_i=max(f_i−1,f_{i−d}+1)$。每段无法到达的部分依然是一个前缀。有以下结论：有值的部分形如先一段值为 $x$，长度 $<d$ 的段，而后是长度为 $d$ 的值为 $x+1,x+2,\cdots$ 的段。这个结论可以类似的归纳证明。所以只需要对于每段求出有值的第一个位置和值与第一个位置不同的第一个位置就可以表示整个 dp 数组。可以用二分套二分维护做到 $O(n\log^2n)$，也可以精细实现做到 $O(n\log n)$。

询问只需要二分找到询问的位置位于那一段内然后就可以快速求值了。